package com.zhugang.week02;

/**
 * @program algorithms
 * @description: getIntersectionNode
 * @author: chanzhugang
 * @create: 2022/05/31 16:24
 */
public class GetIntersectionNode {

    /**
     * 160. 相交链表
     *
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode pA = headA;
        ListNode pB = headB;
        // 在这里第一轮体现在pA和pB第一次到达尾部会移向另一链表的表头, 而第二轮体现在如果pA或pB相交就返回交点, 不相交最后就是null==null
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }

    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        // 分别求两个链表的长度，让长链表先走链表长度差（na - nb），让pA和pB同步进行
        ListNode pA = headA;
        int na = 0;
        while (pA != null) {
            na++;
            pA = pA.next;
        }
        ListNode pB = headB;
        int nb = 0;
        while (pB != null) {
            nb++;
            pB = pB.next;
        }
        // 长链表先走相差节点数
        pA = headA;
        pB = headB;
        if (na >= nb) {
            for (int i = 0; i < na - nb; i++) {
                pA = pA.next;
            }
        } else {
            for (int i = 0; i < nb - na; i++) {
                pB = pB.next;
            }
        }

        while (pA != null && pB != null && pA != pB) {
            pA = pA.next;
            pB = pB.next;
        }
        if (pA == null || pB == null) {
            return null;
        }
        return pA;
    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }
}